/**
 * 
 */
package string;

import java.util.Arrays;

/**
 * Given a string S and a string T, find the minimum window in S which will
 * contain all the characters in T in complexity O(n).
 * 
 * For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".
 * 
 * Note: If there is no such window in S that covers all characters in T, return
 * the emtpy string "".
 * 
 * If there are multiple such windows, you are guaranteed that there will always
 * be only one unique minimum window in S.
 * 
 * @author xyyi
 * @sine 2013/01/13
 * @see 2013/01/13
 * 
 */
public class MinimumWindowSubstring {

	/**
	 * 
	 */
	public MinimumWindowSubstring() {
		// TODO Auto-generated constructor stub
	}

	public String minWindow(String S, String T) {

		int[] charsFoundInS = new int[256];
		int[] charsInT = new int[256];
		Arrays.fill(charsFoundInS, 0);
		Arrays.fill(charsInT, 0);

		for (int i = 0; i < T.length(); i++) {
			charsInT[T.charAt(i)]++;
		}

		int count = 0;
		int minWindowBegin = 0;
		int minWindowLength = Integer.MAX_VALUE;
		for (int begin = 0, end = 0; end < S.length(); end++) {
			if (charsInT[S.charAt(end)] > 0) {
				if (charsFoundInS[S.charAt(end)] < charsInT[S.charAt(end)]) {
					count++;
				}
				charsFoundInS[S.charAt(end)]++;

				if (count == T.length()) {
					while (charsInT[S.charAt(begin)] == 0
							|| charsFoundInS[S.charAt(begin)] > charsInT[S
									.charAt(begin)]) {
						if (charsFoundInS[S.charAt(begin)] > charsInT[S
								.charAt(begin)]) {
							charsFoundInS[S.charAt(begin)]--;
						}
						begin++;
					}

					if (minWindowLength > end - begin + 1) {
						minWindowBegin = begin;
						minWindowLength = end - begin + 1;
					}
				}
			}
		}

		return minWindowLength == Integer.MAX_VALUE ? "" : S.substring(
				minWindowBegin, minWindowBegin + minWindowLength);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		// int x = "1".charAt(0); // String to Character to int
		// int y = 'A'; // Character to int
		// byte[] z = "B|".getBytes(); // String to bytes
		// System.out.println("1=" + x + " A=" + y + " B=" + z[0] + " |=" +
		// z[1]);

		String S = "ADOBECODEBANC";
		String T = "ABC";
		MinimumWindowSubstring mws = new MinimumWindowSubstring();
		System.out.printf("min windows sub is: %s", mws.minWindow(S, T));

	}

}
